
{\magonebf 3.5 Bounded Stacks (b\_stack) }

\decl b\_stack E

{\bf 1. Definition}

An instance $S$ of the parmaterized data type \name\ is a stack 
(see section 2.3) of bounded size. 

\bigskip
{\bf 2. Creation}

\create S (n)   

creates an instance \var\ of type \name\ that can hold up to $n$ elements.
\var\ is initialized with the empty stack.


{\bf 3. Operations}
\+\cleartabs & \hskip 2truecm & \hskip 4truecm &\cr
\+\op E       top   {}        
                              {returns the top element of \var}
\+\nop                        {\precond $S$ is not empty.}
\smallskip
\+\op E       pop   {}        
                              {deletes and returns the top element of \var}
\+\nop                        {\precond $S$ is not empty.}
\smallskip
\+\op void    push  {E\ x}    
                              {adds $x$ as new top element to \var}
\+\nop                        {\precond $S$.size() $< n$.}
\smallskip
\+\op void    clear {}        
                              {makes \var\ the empty stack.}
\smallskip
\+\op int     size  {}        
                              {returns the size of \var.}
\smallskip
\+\op bool    empty {}        
                              {returns true if \var\ is empty, false otherwise.}

\bigskip
{\bf 4. Implementation}

Bounded Stacks are implemented by \CC vectors. All operations take 
time $O(1)$. The space requirement is $O(n)$.

